package gold.digger;

import gold.utils.InputUtil;
import org.apache.commons.collections4.list.TreeList;

import java.util.*;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1567 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int getMaxLen(int[] nums) {
            if (null == nums || nums.length <= 0) return 0;
            if (nums.length == 1) return nums[0] > 1 ? 1 : 0;

            int[] dp = new int[nums.length + 1];
            TreeSet<Integer> zeroPosList = new TreeSet<>();
            TreeSet<Integer> negativePosList = new TreeSet<>();

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < 0) {
                    dp[i + 1] = dp[i] + 1;
                    negativePosList.add(i);
                } else if (nums[i] > 0) {
                    dp[i + 1] = dp[i];
                } else {
                    dp[i + 1] = 0;
                    zeroPosList.add(i);
                }
            }

            int maxLen = 0;
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] == 0) continue;
                int curNumIsNegative = nums[i] < 0 ? 1 : 0;

                Integer furthestZeroPos = zeroPosList.floor(i);
                //从i向前找第一个0值做起点
                Integer startIdx = (null == furthestZeroPos ? 0 : furthestZeroPos + 1);
                while (startIdx < i && (dp[i] - dp[startIdx] + curNumIsNegative) % 2 != 0) {
                    if (nums[startIdx++] < 0) continue;
                    startIdx = (null == negativePosList.ceiling(startIdx) ? i : negativePosList.ceiling(startIdx));
                }
                maxLen = Math.max(maxLen, i - startIdx + 1);
            }

            return maxLen;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[-16,0,-14,4,-13,-17,-19,-17,-21,-11,12]");
        System.out.println(solution.getMaxLen(arr));
    }

    public static void main(String[] args) throws Exception {
        LC1567 an = new LC1567();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
